﻿class Solution
	2 {
3 public:
	4 int lastStoneWeightII(vector<int>&stones)
		5 {
		6 // 1. 准备⼯作
			7 int sum = 0;
		8 for (auto x : stones) sum += x;
		9 int n = stones.size(), m = sum / 2;
		10 // 2. dp
			11 vector<vector<int>> dp(n + 1, vector<int>(m + 1));
		12 for (int i = 1; i <= n; i++)
			13 for (int j = 0; j <= m; j++)
			14 {
			15 dp[i][j] = dp[i - 1][j];
			16 if (j >= stones[i - 1])
				17 dp[i][j] = max(dp[i][j], dp[i - 1][j - stones[i - 1]] +
					stones[i - 1]);
			18 }
		19 // 3. 返回结果
			20 return sum - 2 * dp[n][m];
		21 }
	22 };